package datastructure.tree.bst2;


/**
 * 二叉搜索树-查找节点的前继和后驱节点
 *
 * @author 杨 强
 * @package datastructure.tree.bst2
 * @createTime 2023-03-21 21:50
 */
public class BST01BeforeAfter {
    public static void main(String[] args) {
        /*
                        3
                       / \
                      2   4
                     /
                    1
         */
        TreeNode node1 = new TreeNode(1, "1", null, null);
        TreeNode node2 = new TreeNode(2, "2", node1, null);
        TreeNode node4 = new TreeNode(4, "4", null, null);
        TreeNode node3 = new TreeNode(3, "5", node2, node4);
        BST01BeforeAfter bst01 = new BST01BeforeAfter(node3);

        System.out.println("预计2, 实际:" + bst01.successor(node1.key));

    }

    /**
     * 二叉搜索树的根节点
     */
    TreeNode root;

    public BST01BeforeAfter(TreeNode root) {
        this.root = root;
    }

    /**
     * 查找节点的前驱节点的值
     * @param key 节点key
     * @return 前驱节点的值
     */
    public Object predecessor(int key){
        // 往右走的节点: 对于子节点来说就是往左来的祖先节点
        TreeNode ancestorFromLeft = null;

        // 先找到节点
        TreeNode p = root;
        while (p != null){
            if (key < p.key){
                // 往左
                p = p.left;
            }else if (key > p.key){
                ancestorFromLeft = p;
                // 往右
                p = p.right;
            }else{
                // 找到了
                break;
            }
        }

        // 没有找到
        if (p == null){
            return null;
        }

        // 有左孩子那么前驱就是左边子树最大的节点
        if (p.left != null){
            return max(p.left);
        }

        // 没有左孩子的话就是最近从左边来的祖先节点是前驱节点
        return ancestorFromLeft != null ? ancestorFromLeft.value : null;
    }

    /**
     * 查找节点的后继节点的值
     * @param key 节点key
     * @return 后继节点的值
     */
    public Object successor(int key){
        TreeNode ancestorFromRight = null;
        TreeNode p = root;
        while (p != null) {
            if (key < p.key) {
                ancestorFromRight = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                break;
            }
        }

        if (p == null) {
            return null;
        }
        // 情况1 - 有右孩子
        if (p.right != null) {
            return min(p.right);
        }
        // 情况2 - 有祖先自右而来
        return ancestorFromRight != null ? ancestorFromRight.value : null;
    }

    /**
     * 查找元素-while版
     * @param key 元素的key
     * @return key对应的元素值
     */
    public Object get2(int key){
        TreeNode node = root;
        while (node != null){
            if (node.key > key){
                node = node.left;// 往左找
            }else if (node.key < key){
                node = node.right; // 往右找
            }else {
                return node.value; // 找打
            }
        }
        return null;
    }



    /**
     * 查找节点的子树中最小的节点
     * @return
     */
    public Object min(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        // 左边未走到头
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    /**
     * 查找节点的子树中最大的节点
     * @return
     */
    public Object max(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        // 右边未走到头
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }
}
